The situation is considered where a set of information to be transmitted is represented by a sequence of symbols belonging to the set {0,1}. This set is referred to as the binary alphabet and its elements are referred to as binary elements or bits.
In order to transmit these binary elements, they are converted into electrical quantities. For example, the bit 0 is represented by a positive electrical signal and the bit 1 by a negative electrical signal. These electrical signals have the same absolute value, which is here arbitrarily chosen so as to be equal to 1 in order to simplify the description. However, in reality, these signals can take any value deemed appropriate according to the envisaged application, such as, for example, an electrical voltage of ±5 volts.
When these electrical signals are transmitted over a transmission channel impaired by noise, the received values differ from the transmitted values.
In particular, if the transmission channel is impaired by a white Gaussian noise, the received value a corresponding to a transmitted symbol a belonging to the set {−1,+1} is a random variable whose probability density is given by p(α|a)=(σ√{square root over (2π)})−1exp[−(a−α)2/2σ2], where the parameter σ is specified by the signal to noise ratio of the transmission channel: σ=√{square root over (N/2E)} where N is the spectral power density of the noise and E is the energy of the signal transmitted.
The probability that the symbol a has been transmitted, if α is the symbol received, is denoted P(a|α). The value of ρ(α)=P(−1|α)/P(+1|α) can be used to obtain an estimation â of the transmitted symbol a, received in the form of α: if ρ(α)>1 then â is chosen so as to be equal to −1 and if ρ(α)<1 then â is chosen so as to be equal to +1.
For the purpose of limiting the effect of the noise on the efficacy of the transmission of information, it is known that an error correcting encoding can be implemented, which consists of using only a small proportion of all the possible sequences for representing the information.
An example of such an error correcting encoding is block linear encoding: the binary sequence to be transmitted is a sequence of words of n binary elements, n being a positive integer, each of these words being chosen in the subset C of the words v of length n which satisfy v·HT=0, where H is a matrix of dimension (n−k)×n on the set {0,1}, 0 is the (n−k)-tuplet of zeros and T represents the transposition, k being an integer less than n. In addition, the components of the matrix product v·HT are calculated modulo 2.
It is well known to a person skilled in the art that any word v of the code C satisfies v·hT=0 for any binary n-tuplet h which is the result of a linear combination of the rows of the matrix H. It should be noted that, in this context, the expression “linear combination” implies that the coefficients which define it are themselves binary elements and the result is always to be reduced modulo 2.
The set of words h thus obtained is referred to as the orthogonal code or dual of the code C and is generally denoted C⊥. Let us consider a word h of C⊥ whose weight is w (w being an integer less than n), which means that it contains w binary elements equal to 1 and n−w binary elements equal to 0.
Assume, in order to simplify, that these w binary elements equal to 1 appear in the first w positions of h: h=(1, . . . , 1, 0, . . . , 0). Let v=(v1, . . . , vn). The equation v·hT=0 therefore means             ∑              i        =        1            w        ⁢          v      i        =  0modulo 2. It implies in particular:v1=v2+v3+ . . . +vw modulo 2  (1)and, more generally,vi=v1+ . . . +vi−1+vi+1+ . . . +vw modulo 2  (2)for any integer i between 1 and w.
Let a=(a1, . . . , an) be the sequence of electrical signals transmitted belonging, in order to simplify, to {−1,+1} and representing the binary n-tuplet v. Let α=(α1, . . . , αn) be the corresponding received sequence. Equations (1) and (2) above show that, given h, there are, for each of the first w binary values vi, two independent items of information which can be extracted from α. The first is the received value αi, from which it is possible to calculate ρ(αi) as explained above. The second is the set, denoted A(i,h), of the values αj, j=1, . . . , i−1, i+1, . . . , w. This is because, for any i, the values αj of A(i,h) are a noisy image of the corresponding symbols aj, which are a faithful translation of the corresponding binary elements vj.
In order to explain this second item of information, said to be extrinsic, on vi, the quantity z=exp(−2/σ2)=exp(−4E/N) is introduced, which depends on the signal to noise ratio of the transmission channel in question, and there are defined:S1(i)=Σzαj,αjεA(i,h),S2(i)=Σzαj+αk,αj, αkεA(i,h),j<k,S3(i)=Σzαj+αk+αl,αj,αk,αlεA(i,h),j<k<l, . . . Sw−1(i)=zα1+ . . . +αi−1+αi+1+ . . . +αw
P[ai|A(i,h)] is defined as being the probability that the ith signal transmitted was ai given the symbols αj of A(i,h). The quantity ρext[A(i,h)]=P[ai=−1|A(i,h)]/P[ai=+1|A(i,h)] supplies “additional information” on the value of the transmitted symbol ai.
It can be shown that the quantities ρext[A(i,h)] have a very simple expression according to the polynomials Sr(i) introduced above:ρext[A(i,h)]=[S1(i)+S3(i)+ . . . ]/[1+S2(i)+S4(i)+ . . . ]
When methods of the probabilistic type are used for estimating what was the transmitted sequence (or only some of its binary elements), the following problem is posed: it is sought to determine the quantities ρext[A(i,h)] for i=1, . . . , w with a calculation cost as low as possible, on the basis of the w binary elements received represented by the received signals αj, corresponding to a word h of the code C⊥.